//
// Created by 25446 on 2023/3/10.
//

#include "interface.h"
#include "graph.h"
#include "pch.h"
#include "error.h"

#pragma warning(disable:4267)

void reconstruct(Node *nodes, int len, int h, int ban) {
    if (ban > 0) {
        for (int i = 0; i < len; i++) {
            if (nodes[i].get_head() == ban) {
                nodes[i].set_disabled(true);
            }
        }
    }

    if (h > 0) {
        std::queue<int> que;

        for (int i = 0; i < len; i++) {
            nodes[i].reset_ind();
            if (nodes[i].get_ind() == 0 && nodes[i].get_head() != h) {
                que.push(i);
            }
        }
        while (!que.empty()) {
            int top = que.front();
            que.pop();
            nodes[top].set_disabled(true);

            for (int i = 0; i < nodes[top].get_oud(); i++) {
                nodes[nodes[top].get_to(i)].ind_dec();
                if (nodes[nodes[top].get_to(i)].get_ind() == 0 && nodes[nodes[top].get_to(i)].get_head() != h) {
                    que.push(nodes[top].get_to(i));
                }
            }
        }
    }
}

void dfs_r(Node node, int cnt, Node *nodes, vector<int> &tmp, vector<int> &ans, int &maxlen, int type, int tail) {
    int size = node.get_oud();
    tmp.push_back(node.get_id());
    if (type == 1) {
        cnt += 1;
    } else if (type == 2) {
        cnt += node.get_len();
    }
    for (int i = 0; i < size; i++) {
        int to = node.get_to(i);
        if (!nodes[to].is_used() && !nodes[to].is_disabled()) {
            nodes[to].set_used(true);

            dfs_r(nodes[to], cnt, nodes, tmp, ans, maxlen, type, tail);

            nodes[to].set_used(false);
        }
    }
    if (cnt > maxlen && (tail == 0 || node.get_tail() == tail)) {
        maxlen = cnt;
        ans = tmp;
    }
    tmp.pop_back();
}

int gen_chain_loop(char *words[], int len, char *result[], int head, int tail, int banned, int type,Node* nodes) {
//    Node *nodes = create_graph(words, len);
    if (banned > 0) {
        for (int i = 0; i < len; i++) {
            if (nodes[i].get_head() == banned) {
                nodes[i].set_disabled(true);
            }
        }
    }
    int maxlen = 0;
    vector<int> ans;
    vector<int> tmp;
    for (int i = 0; i < len; i++) {
        if (!nodes[i].is_disabled() && (head == 0 || nodes[i].get_head() == head)) {
            nodes[i].set_used(true);
            //type1是-w，type2是-c
            dfs_r(nodes[i], 0, nodes, tmp, ans, maxlen, type, tail);
            nodes[i].set_used(false);
        }
    }

    int num = ans.size();
//    for (int i = 0; i < num; ++i) {
//        cout << nodes[ans[i]].get_body() << endl;
//    }
    for (int i = 0; i < num; i++) {
        char *tmpp = (char *) std::malloc(std::strlen(nodes[ans[i]].get_body().c_str()) * sizeof(char));
        strcpy(tmpp, nodes[ans[i]].get_body().c_str());
        result[i] = tmpp;
    }
    return num;
}

int gen_chain_char(char* words[], int len, char* result[], int head, int tail, int reject, int enable_loop) {
    if (head == reject && head != 0) {
        cerr << "-h -j has the same char" << endl;
        return -PARA_FORM_ERROR;
    }
    int *dp = (int *) malloc((len + 5) * sizeof (int));
    int topo_list[len + 5];
    Node * nodes = create_graph(words, len);
    for (int i = 0;i < len;i++) {
        dp[i] = nodes[i].get_len();
    }
    int r = topo_sort(nodes, len, topo_list);
    if (!enable_loop || r == 0) {
        if(r == -1) {
            cerr << "Find Loop,but !enable_loop!" << endl;
        }
        reconstruct(nodes,len ,head, reject);
        for(int i = 0;i < len;i++) {
            int u = topo_list[i];
            if(!nodes[u].is_disabled()) {
                int size = nodes[u].get_oud();
                for(int j = 0;j < size;j++) {
                    int to = nodes[u].get_to(j);
                    if (!nodes[to].is_disabled()) {
                        if(dp[to] < dp[u] + nodes[to].get_len()) {
                            dp[to] = dp[u] + nodes[to].get_len();
                            nodes[to].set_pre(u);
                        }
                    }
                }
            }
        }
        int maxLen = -100;
        int last = -1;
        if (tail == 0) {
            for (int i = 0;i < len;i++) {
                if(!nodes[i].is_disabled() &&  maxLen < dp[i] && dp[i] > nodes[i].get_len()) {
                    maxLen = dp[i];
                    last = i;
                }
            }
        }
        else {
            for(int i = 0;i < len;i++) {
                if (!nodes[i].is_disabled() && maxLen < dp[i] && nodes[i].get_tail() == tail && dp[i] > nodes[i].get_len()) {
                    maxLen = dp[i];
                    last = i;
                }
            }
        }
        if (last != -1) {
            int cnt = 0;
            char* backup[10005];
            while(nodes[last].get_pre() != -1) {
//                strcpy(result[--cnt] ,nodes[last].get_body().c_str());
                char *tmp = (char *)std::malloc(nodes[last].get_body().size() * sizeof(char ));
                strcpy(tmp ,nodes[last].get_body().c_str());
                backup[cnt++] = tmp;
//                result[--cnt] = (char*)nodes[last].get_body().c_str();
                last = nodes[last].get_pre();
            }
//            strcpy(result[--cnt] ,nodes[last].get_body().c_str());
            char *tmp = (char *)std::malloc(nodes[last].get_body().size() * sizeof(char ));
            strcpy(tmp ,nodes[last].get_body().c_str());
            backup[cnt++] = tmp;
            if (cnt == 1) {
                cerr << "can't find ans!" << endl;
                return -NO_ANS;
            }
            for (int i = cnt - 1;i >= 0;i--) {
                result[cnt - 1 - i] = backup[i];
            }
            return maxLen;
        }
        else {
            cerr << "Can find ans" << endl;
            return -NO_ANS;
        }
    }
    else {
        int r = gen_chain_loop(words, len,result, head, tail,reject,enable_loop,nodes);
        if (r > 1){
            return r;
        }
        else {
            cerr << "can't find ans!" << endl;
            return -NO_ANS;
        }
    }
}


int gen_chain_word(char* words[], int len, char* result[], int head, int tail, int banned, int enable_loop){
    if (head == banned && head != 0) {
        cerr << "-h -j has the same char" << endl;
        return -PARA_FORM_ERROR;
    }
    int *dp = (int *) malloc((len + 5) * sizeof (int));
    for (int i = 0;i < len;i++) {
        dp[i] = 1;
    }
    int topo_list[len + 5];
    Node * nodes = create_graph(words, len);
    int r = topo_sort(nodes, len, topo_list);
    if (!enable_loop || r == 0) {
        if(r == -1) {
            cerr << "Find Loop,but !enable_loop!" << endl;
            return -HAVE_LOOP;
        }
        reconstruct(nodes,len ,head, banned);
        for(int i = 0;i < len;i++) {
            int u = topo_list[i];
            if(!nodes[u].is_disabled()) {
                int size = nodes[u].get_oud();
                for(int j = 0;j < size;j++) {
                    int to = nodes[u].get_to(j);
                    if (!nodes[to].is_disabled()) {
                        if(dp[to] < dp[u] + 1) {
                            dp[to] = dp[u] + 1;
                            nodes[to].set_pre(u);
//                            cout << u << to << endl;
                        }
                    }
                }
            }
        }
//        for(int i = 0;i < len;i++) cout << dp[i] << endl;
        int maxLen = -100;
        int last = -1;
        if (tail == 0) {
            for (int i = 0;i < len;i++) {
                if(!nodes[i].is_disabled() &&  maxLen < dp[i] && dp[i] > 1) {
                    maxLen = dp[i];
                    last = i;
                }
            }
        }
        else {
            for(int i = 0;i < len;i++) {
                if (!nodes[i].is_disabled() && maxLen < dp[i] && nodes[i].get_tail() == tail && dp[i] > 1) {
                    maxLen = dp[i];
                    last = i;
                }
            }
        }
        if (last != -1) {
            int cnt = dp[last];
            if (cnt <= 1) {
                cerr << "can't find ans" << endl;
                return -NO_ANS;
            }
            while(nodes[last].get_pre() != -1) {
                char *tmp = (char *)std::malloc(nodes[last].get_body().size() * sizeof(char ));
                strcpy(tmp ,nodes[last].get_body().c_str());
                result[--cnt] = tmp;
                last = nodes[last].get_pre();
            }
            char *tmp = (char *)std::malloc(nodes[last].get_body().size() * sizeof(char ));
            strcpy(tmp ,nodes[last].get_body().c_str());
            result[0] = tmp;
            return maxLen;
        }
        else {
            cerr << "Can't find ans" << endl;
            return -NO_ANS;
        }
    }
    else {
        int r = gen_chain_loop(words, len,result, head, tail,banned,enable_loop,nodes);
        if (r > 1) {
            return r;
        }
        else {
            cerr << "can't find ans!" << endl;
            return -NO_ANS;
        }
    }
}

void dfs(Node node, string str, int cnt, Node* nodes, vector<string> &ans) {
    int size = node.get_oud();
    for (int i = 0;i < size ;i++) {
        int to = node.get_to(i);
        if (!nodes[to].is_used()) {
            nodes[to].set_used(true);
            dfs(nodes[to], str + " " + nodes[to].get_body(), cnt + 1, nodes, ans);
            nodes[to].set_used(false);
        }
    }
    if (cnt > 1) {
        ans.push_back(str);
        // cout << str << endl;
    }
}

int gen_chains_all(char* words[], int len, char* result[]){
    Node * nodes = create_graph(words, len);
    int topo_list[len + 5];
    if (topo_sort(nodes, len,topo_list) == -1) {
        cerr << "Find Loop,but !enable_loop!" << endl;
        return -HAVE_LOOP;
    }
    vector<string> ans;
    for(int i = 0;i < len;i++) {
        nodes[i].set_used(true);
        dfs(nodes[i], nodes[i].get_body(), 1, nodes, ans);
        nodes[i].set_used(false);
    }
    int i = 0;
    for (const auto& s : ans) {
        result[i++] = (char*)s.c_str();
    }
    return ans.size();
}

